package org.hot100_1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class leetcode56 {

//    List<List<String>> res = new ArrayList<>();
//    Deque<String> deque = new LinkedList<>();
//    public List<List<String>> partition(String s) {
//        backtracking(s,0);
//        return res;
//    }
//
//    private void backtracking(String s ,int startIndex){
//        if (startIndex>s.length()-1){
//            res.add(new ArrayList<>(deque));
//            return;
//        }
//
//        for (int i = startIndex; i <s.length(); i++) {
//            if (isPalindrome(s,startIndex,i)){
//                //这里使用i+1的原因：substring方法是截取到i+1之前，不包含i+1
//                String str = s.substring(startIndex,i+1);
//                deque.add(str);
//            }else {
//                continue;
//            }
//            backtracking(s,i+1);
//            deque.removeLast();
//        }
//    }
//
//    private boolean isPalindrome(String str,int startIndex,int EndIndex){
//
//        while (startIndex<=EndIndex){
//            if (str.charAt(startIndex)!=str.charAt(EndIndex)){
//                return false;
//            }
//            startIndex++;
//            EndIndex--;
//        }
//
//        return true;
//    }

    List<List<String>> res =new ArrayList<>();
    LinkedList<String> item =new LinkedList<>();
    public List<List<String>> partition(String s) {
        backtracking(s,0);
        return res;
    }

    private void backtracking(String s,int statIndex){
        if (statIndex==s.length()){
            res.add(new ArrayList<>(item));
            return;
        }

        for (int i = statIndex; i <s.length(); i++) {
            if (isPartition(s,statIndex,i)){
                String partition = s.substring(statIndex, i + 1);
                item.add(partition);
                backtracking(s,i+1);
                item.removeLast();
            }
        }
    }

    private boolean isPartition(String str,int left,int right){

        while (left<right){
            if (str.charAt(left)!=str.charAt(right)){
                return false;
            }
            left++;
            right--;
        }

        return true;
    }



    public static void main(String[] args) {
        String str = "zhang";
        String partStr = str.substring(0,3);
        System.out.println(partStr);
    }
}
